# @author : sentry
# @since : 2023-09-10
# 二分查找

"""
二分法适用情况：
1、必须是有序的序列。
2、对数据量大小有要求。
3、数据量太小不适合二分查找，与直接遍历相比效率提升不明显。
4、数据量太大也不适合用二分查找，因为数组需要连续的存储空间，若数据量太大，往往找不到存储如此大规模数据的连续内存空间

二分查找法
[5,7,11,22,27,33,39,52,58]
以上有序数列中是否存在11，索引值为几
"""

arr_list = [5, 7, 11, 22, 27, 33, 39, 52, 58]
# 第一种 纯算法的方式
number = 7
count = 0
left = 0
right = len(arr_list) - 1
while left <= right:
    middle = (left + right) // 2
    count += 1
    if number < arr_list[middle]:
        right = middle - 1
    elif number > arr_list[middle]:
        left = middle + 1
    else:
        print(f'{number}数字已找到，索引值为{middle}')
        break
else:
    print(f'数字{number}不存在')
print(f'一共使用了{count}次查找')


# 第二种 递归函数的方式
def binary_search(num, le, ri):
    if le > ri:
        return -1
    one_half = (le + ri) // 2
    if num < arr_list[one_half]:
        ri = one_half - 1
    elif num > arr_list[one_half]:
        le = one_half + 1
    else:
        return one_half
    return binary_search(num, le, ri)


print(binary_search(13, 0, len(arr_list) - 1))
